Thành viên đầu tiên của chi được Linnaeus mô tả là quạ mỏ đỏ dưới danh pháp Upupa pyrrhocorax trong sách Systema Naturae năm 1758. Chi Upupa của ông chứa các loài có mỏ cong dài và lưỡi tù ngắn. Chúng bao gồm cò quăm hói phương bắc và đầu rìu, những loài chim mà hiện nay người ta biết là không có quan hệ họ hàng gì với quạ chân đỏ.[2]

Quạ mỏ vàng được Linnaeus mô tả như là Corvus graculus trong ấn bản năm 1766 của Systema Naturae.[3] Mặc dù Corvus là chi quạ mà các họ hàng của quạ chân đỏ thuộc về, nhưng chúng là đủ khác biệt để nhà điểu học người Anh là Marmaduke Tunstall chuyển sang chi mới là Pyrrhocorax trong sách phát hành năm 1771 là Ornithologia Britannica,[4] Tên gọi của chi này có nguồn gốc từ tiếng Hy Lạp cổ đại πύρρος (purrhos) nghĩa là "màu đỏ lửa" và κόραξ (korax) nghĩa là "quạ".[5]

Trước đây người ta cho rằng các họ hàng gần gần nhất của quạ chân đỏ là quạ điển hình (Corvus), đặc biệt là gần với quạ gáy xám (Corvus subgen. Coloeus, nay là chi Coloeus).[6]

Tuy nhiên các nghiên cứu phát sinh chủng loài phân tử gần đây chỉ ra rằng quạ chân đỏ có quan hệ họ hàng gần với khách đuôi cờ (Temnurus temnurus) và chúng tạo thành một nhánh là chị em với phần còn lại của Corvidae.[7]

Các loài của chi Pyrrhocorax khác với Corvus ở chỗ chúng có mỏ và chân với màu sắc rực rỡ, khối xương cổ chân trơn mượt và không có vảy và các lông mũi rất ngắn và rậm.[8] Quạ chân đỏ có bộ lông màu đen thuần nhất, không có các vùng nhạt màu như ở một số loài trong chi Corvus.[8] Hai loài Pyrrhocorax cũng là vật chủ chính của 2 loài bọ chét chuyên ký sinh trên quạ chân đỏ là Frontopsylla frontalis và F. laetus, thông thường không thấy ở chim dạng quạ.[9]